package com.clstu.graph.graphfordij;


import java.util.*;

/**
 * 图研究,专门针对dij..算法(结合定制小根堆)
 */
public class Graph {
    //点集和边集构成的就是图
    List<Node> nodes = null;
    List<Edge> edges = null;
    //构造器
    public Graph(List<Node> nodes,List<Edge> edges){
        this.edges = edges;
        this.nodes = nodes;
    }

    public static void main(String[] args) {
        //测试一下
        int[][] g= {{0,5,17,20,0}, {5,0,2,0,4}, {17,2,0,1,0}, {20,0,1,0,5}, {0,4,0,5,0}};
        Graph graph = Graph.createGraph(g);
        System.out.println(graph.nodes.get(0));
        System.out.println(dijkstra(graph.nodes.get(0),5));
    }

    //编写方法根据邻接矩阵创建图返回
    public static Graph createGraph(int[][] g){
        ArrayList<Node> nodes = new ArrayList<>();
        for (int i = 0; i < g.length; i++) {
            nodes.add(new Node(String.valueOf((char) ('A' + i))));
        }
        //连接边
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g.length; j++) {
                if(g[i][j] != 0){
                    int weight = g[i][j];
                    Node from = nodes.get(i);
                    Node to = nodes.get(j);
                    //创建边
                    Edge edge = new Edge(from, to, weight);
                    edges.add(edge);
                    from.nexts.add(to);
                    from.connectedEdges.add(edge);
                    from.out++;
                    to.in++;
                }
            }
        }
        //返回创建号的图
        return new Graph(nodes,edges);
    }

    /**
     * 点类
     */
    public static class Node{
        int in = 0;//入度,
        int out = 0;//出度
        String name;//地点名称
        Set<Node> nexts = null;//邻接节点集
        Set<Edge> connectedEdges = null;//以自身出发的边集
        //构造器
        public Node(String name){
            this.name = name;
            nexts = new HashSet<>();
            connectedEdges = new HashSet<>();
        }

        @Override
        public String toString() {
            return "Node{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

    /**
     * 边类
     */
    public static class Edge{
        Node from = null;//起点
        Node to = null;//重点
        int weight = 0;//权重
        //构造器
        public Edge(Node from,Node to,int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * 定制类,节点和起点的距离组成
     */
    public static class Record{
        Node node;
        int distance;
        //构造器
        public Record(Node node,int distance){
            this.node = node;
            this.distance = distance;
        }
    }
    /**
     * 定制堆,按照距离比较的 小根堆 (注意是小根堆,不要脑抽写成大根堆!!!!!!!!!!!!!!)
     */
    public static class NodeHeap{
        Node[] heap;
        HashMap<Node,Integer> disMap = new HashMap<>();
        HashMap<Node,Integer> indexMap = new HashMap<>();
        int heapSize = 0;
        int maxSize = 0;
        //构造器
        public NodeHeap(int maxSize){
            this.maxSize = maxSize;
            heap = new Node[maxSize];
        }

        public boolean isEmpty(){
            return heapSize == 0;
        }

        public Record poll(){
            Record res = new Record(heap[0], disMap.get(heap[0]));
            //调整堆
            swap(0,heapSize-1);
            indexMap.put(heap[heapSize-1],-1);
            heap[--heapSize] = null;
            if(heapSize!=0) {
                heapFy(heap[0]);
            }
//            System.out.println("poll 成功");
            return res;
        }

        //编写方法实现heapFy,向下调整到正确的位置
        public void heapFy(Node node){
//            System.out.println(node);
            int index = indexMap.get(node);
            for (int i = index*2+1;i<heapSize;i=i*2+1){
                //找到更大的孩子
                if(i+1<heapSize && disMap.get(heap[i+1])>disMap.get(heap[i])){
                    i++;
                }
                //跟更大的孩子比较
//                System.out.println(i);
                if(disMap.get(heap[i]) < disMap.get(heap[index])){
                    heap[index] = heap[i];
                    indexMap.put(heap[index],index);
                    index = i;
                }
            }
            heap[index] = node;
            indexMap.put(heap[index],index);
        }

        //编写方法,实现heapInsert,向上找跳到正确的位置
        public void heapInsert(Node node){
            for (int i = heapSize-1;i>=0 ;i = (i-1)/2){
                if(disMap.get(heap[i]) < disMap.get(heap[(i-1)/2])){
                    swap(i,(i-1)/2);
                }else {
                    break;
                }
            }
        }

        //编写方法,实现add
        public void addOrUpdateOrIgnore(Node node,int distance){
            //分3种情况: 新节点 添加过
            if(!indexMap.containsKey(node)){
                heap[heapSize++]=node;
                disMap.put(node,distance);
                indexMap.put(node,heapSize-1);
                heapInsert(node);
            }else if(indexMap.get(node) == -1){
                //如果弹出过,说明已经确定了最短,不用管了
            }else {
                //如果距离确实更小了,跟新调整
//                System.out.println("distance = "+distance);
                if(distance < disMap.get(node)){
                    disMap.put(node,distance);
                    heapInsert(node);
                }
            }
//            System.out.println("插入成功");
        }

        //编写方法实现swap
        public void swap(int index1,int index2){
            Node temp = heap[index1];
            indexMap.put(heap[index1],index2);
            indexMap.put(heap[index2],index1);
            heap[index1] = heap[index2];
            heap[index2] = temp;
        }
    }

    //编写方法,实现dij..算法找到所有节点的最近位置
    public static HashMap<Node,Integer> dijkstra(Node start,int size){
        HashMap<Node, Integer> res = new HashMap<>();
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(start,0);//先将头节点入堆
        //依次遍历,
        int count = 0;
        while (!nodeHeap.isEmpty()){
            Record poll = nodeHeap.poll();
            //这个点已经确定
            res.put(poll.node,poll.distance);
            //添加周围的节点
            for (Edge edge : poll.node.connectedEdges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to,poll.distance+edge.weight);
            }
        }
        //返回结果集合即可
        return  res;
    }
}

